package com.company.剑指offer每日刷题.普通版;

/**
 * 剑指 Offer 42. 连续子数组的最大和
 * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 *
 * 要求时间复杂度为O(n)。
 * 示例1:
 *
 * 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出: 6
 * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 * 提示：
 *
 * 1 <= arr.length <= 10^5
 * -100 <= arr[i] <= 100
 * */
public class MaxSubArray {

    /**
     * 方法：动态规划
     * 思路：
     *    求类似的连续子数组的和的问题，可以利用前缀和来计算
     *    定义： 令 nums数组的前0~i项的数组元素中包含的所有子数组的和的最大值为   dp[i]
     *          令 nums[0:n]的的前缀和的数组为： S[0:(n+1)]，且 S(0) = 0,S(i) = nums[0~(i-1)]的和 ,有 i <= j，满足
     *         nums[i] + nums[i+1] +...+ nums[j] = S(j) - S[i-1]，这个时候，就将问题转化成了和《Offer 63. 股票的最大利润》一题类似的场景了。
     *    初始条件：
     *          dp[0] = nums[0];
     *    状态转移方程：
     *        dp[i] = max(dp[i-1],S(i+1) - min(S[0:(i)]))
     *        为什么这里没有计算是 min(S[0:(i)]) 而不是 min(S[0:(i+1)])呢？
     *        因为是用前缀和的差值表示 某一连续子数组的和，如果 S(i+1) 就是当前的最小前缀和，减去本身就表示这个子数组的长度为0，不包含任何元素，没有意义了。
     *    优化：
     *          可以将 min(S[0:(i+1)]) 替换成一个 临时变量，每次遍历值的时候更新最小值。
     * */
    public int maxSubArray(int[] nums) {
        int sum = 0;    //nums[0:i] 的和
        int minPreSum = 0 ;     //nums[0:i] 的所有的前缀和中的最小值
        int res = nums[0];      //结果
        for (int i = 0; i < nums.length; i++) {
            minPreSum = Math.min(sum,minPreSum);
            sum += nums[i];
            res = Math.max(res,sum - minPreSum);
        }
        return res;
    }

    public static void main(String[] args) {
        MaxSubArray obj = new MaxSubArray();
        int res = obj.maxSubArray(new int[]{-2});
        System.out.println(res);
    }
}
